package com.niuke;

import com.leetCode.tree.TreeNode;

import java.util.*;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-15 15:10:40
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-15     张李鑫                     1.0         1.0 Version
 */
public class JZ77 {
    /**
     * 述
     * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
     * <p>
     * 数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 100∣val∣<=100
     * 要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)
     * 例如：
     * 给定的二叉树是{1,2,3,#,#,4,5}
     */
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }
        //定义指针
        TreeNode pre = pRoot;
        TreeNode next = null;

        //定义容器
        Queue<TreeNode> stack = new LinkedList<>();
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> child = new ArrayList<>();

        boolean flag = true;
        stack.add(pRoot);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.poll();
            if (flag) {
                child.add(pop.val);
            } else {
                child.add(0, pop.val);
            }
            if (pop.left != null) {
                stack.add(pop.left);
                next = pop.left;
            }

            if (pop.right != null) {
                stack.add(pop.right);
                next = pop.right;
            }

            if (pre == pop) {
                lists.add(child);
                child = new ArrayList<>();
                pre = next;
                flag = !flag;
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(5);


        treeNode.left = treeNode1;
        treeNode.right = treeNode2;

        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;


        System.out.println(Print(treeNode));

    }
}

